$O(N)$ Iterative and $O(NlogN)$ Fast Direct Volume Integral Equation Solvers with a Minimal-Rank ${\cal H}^2$-Representation for Large-Scale $3$-D Electrodynamic Analysis

摘要

Linear complexity iterative and log-linear complexity direct solvers aredeveloped for the volume integral equation (VIE) based general large-scaleelectrodynamic analysis. The dense VIE system matrix is first represented by anew cluster-based multilevel low-rank representation. In this representation,all the admissible blocks associated with a single cluster are grouped togetherand represented by a single low-rank block, whose rank is minimized based onprescribed accuracy. From such an initial representation, an efficientalgorithm is developed to generate a minimal-rank ${\cal H}^2$-matrixrepresentation. This representation facilitates faster computation, and ensuresthe same minimal rank's growth rate with electrical size as evaluated fromsingular value decomposition. Taking into account the rank's growth withelectrical size, we develop linear-complexity ${\cal H}^2$-matrix-based storageand matrix-vector multiplication, and thereby an $O(N)$ iterative VIE solverregardless of electrical size. Moreover, we develop an $O(NlogN)$ matrixinversion, and hence a fast $O(NlogN)$ \emph{direct} VIE solver for large-scaleelectrodynamic analysis. Both theoretical analysis and numerical simulations oflarge-scale $1$-, $2$- and $3$-D structures on a single-core CPU, resulting inmillions of unknowns, have demonstrated the low complexity and superiorperformance of the proposed VIE electrodynamic solvers. %The algorithmsdeveloped in this work are kernel-independent, and hence applicable to other IEoperators as well.